// 给定一个数组nums，找出数组排序之后，相邻元素之间最大的差值，如果数组元素个数小于2，则返回0
// 在时间复杂度和空间复杂度都为线性复杂度
// 所有元素都是非负整数，且数值在32位有符号整数范围内
// 时间复杂度：O(n * k)
// 空间复杂度：O(n + k)

// 思路，利用基数排序

function maximumGap(arr) {
    function radixSort(arr) {
        let size = String(Math.max(...arr)).length
        for (let i = 0; i < size; i++) {
            let bucketArr = new Array(10).fill(0).map(_ => [])
            for (let j = 0; j < arr.length; j++) {
                const index = Math.floor((arr[j] / Math.pow(10, i))) % 10
                bucketArr[index].push(arr[j])
            }  
            arr = []
            for (const item of bucketArr) {
                arr = [...arr, ...item]
            } 
        }
        return arr
    }
    if (arr.length < 2) {
        return 0
    }
    arr = radixSort(arr)
    let maxGAP = 0
    for (let i = 0; i < arr.length - 1; i++) {
        maxGAP = Math.max(maxGAP, arr[i+1] - arr[i])
    }
    return maxGAP
}

let arr = [3, 65, 98, 1]
console.log(maximumGap(arr))
